1. Field of the Invention
The present invention relates generally to a tree decoding method for decoding the linear block code, and more particularly, to a tree decoding method which decreases the edges required for decoding by utilizing parity bits in advance, so as to achieve a lower decoding complexity.
2. The Prior Arts
Due to the channel impairment and the undesired noise interference, information may likely be corrupted by errors in the transmission. Accordingly, error-correcting codes are usually needed for allowing the receiver end to correct the error-corrupted information. The class of linear block codes is an important class of error-correcting codes. Typical linear block codes include turbo code, low density parity check (LDPC) codes, quadratic residue (QR) codes, extended quadratic residue (EQR) codes, Bose-Chaudhuri Hocquenghem (BCH) codes and many more.
A linear block code can be encoded by multiplying a k×n generator matrix G with k information bits (u0, u1, . . . , uk−1), thus generating an n-bit codeword c=(c0, c1, . . . , cn−1). Then, a signal, ((−1)c0, (−1)c1, . . . , (−1)cn−1), is transmitted into the channel. With respect to the linear block code, the receiver end decodes the received signal, r=(r0, r1, . . . , rn−1), to recover the information bits, where ri is an error-corrupted version of (−1)ci.
Supposing that the codeword c=(c0, c1, . . . , cn−1) generated by the generator matrix G includes k information bits and n-k parity bits, G is therefore a systematic generator matrix. Specifically, when the 0 to (k−1)th columns constitute a k×k identity matrix, the information bits (u0, u1, . . . , uk−1) correspond to a codeword (c0, c1, . . . , cn−1)=(u0, u1, . . . , uk−1, pk, . . . , pn−1), where pk, . . . , pn−1 are parity bits. In such a way, a code tree can be obtained in accordance with the generator matrix G.
Taking an (n, k)=(8, 4) extended Hamming code as an example for illustration, the amount of the information bits is k=4. The transmission end utilizes a generator matrix G as shown in FIG. 1a to encode the 4-bit information (k=4) into a codeword having a length of n=8. In such a way, a code tree as shown in FIG. 1b can be obtained in accordance with the generator matrix G as shown in FIG. 1a. The code tree starts to emanate from the root node of level 0. With respect to the prior k (i.e., 4 hereby) levels (i.e., levels 0, 1, 2, and 3 hereby), each node can be bifurcated into two edges, and each of the two edges represents a distinctive information bit, in which a solid line represents an information bit of 0, and a dashed line represents an information bit of 1. With respect to the latter n-k levels (i.e., levels 4, 5, 6, and 7 hereby), each node emanates into a single edge, which represents a parity bit. For example, a node of level j represents a partial path (c0, c1, . . . , cj−1). A node at level n=8 corresponds to a complete path, that is a codeword, i.e., (c0, c1, . . . , cn−1). A node of level n is known as a goal node. During the process of emanating from the root node to the goal nodes, we have different paths which represent different codewords. For example, the uppermost path shown in FIG. 1b is completely constituted of solid lines, which the codeword 00000000 encoded from the information 0000.
The tree decoding process of the receiver end is to obtain path metrics according to the received signal r with respect to all of the paths (i.e., codewords). Then, a path having a best metric is selected as a decoded codeword. When an exhaustive search decoding mode is adopted, there would be 2k paths to be calculated to obtain the path metrics. In this manner, the calculation complexity exponentially increases in accordance with k.
For purpose of Finding a solution of the complexity, Laura Ekroot published a thesis titled “A* Decoding of Block Codes” in volume 44 of IEEE Transactions on Communications (pages 1052 to 1056). In this paper, there is disclosed a method based on Dijkstra's algorithm using artificial intelligence, which is applied for the maximum-likelihood decoding of linear block codes. The A* decoding procedure as disclosed by Laura :Ekroot is as following.
Supposing that the transmitted codeword is c=(c0, c1, . . . , cn−1)=(00111010), where n represents the length of the codeword, and the transmitted signal is ((−1)ca, (−1)ct, . . . , (−1)cn−1)=(1, 1, −1, −1, −1, 1, −1, 1). After the transmission, the signal received at the receiver end is r=(r0, r1, rn−1)=(0.6, 1.8, −1.1, −1.3, 0.9, 1.6, −1.0, −0.5), which is obtained by adding the noise signal to (1, 1, −1, −1, −1, 1, −1, 1). All elements of r are rearranged in accordance with reliabilities thereof (absolute values of ri), thus obtaining r*=(1.8, 1.6, −1.3, −1.1, −1.0, 0.9. 0.6, −0.5). Correspondingly, the generator matrix G is conducted with column exchanging in accordance with position change from r to r*, so as to obtain G*. Further, G* is applied with row operations to obtain a new systematic generator matrix of which 0 to (k−1)th columns constitute a k×k identity matrix. However, for some matrices, such as the present G*, there is no way to obtain such a systematic generator matrix of which 0 to (k−1)th columns can constitute a k×k identity matrix by simply applying row operations. Under this circumstance, the sequence must be adaptively adjusted to obtain a new generator matrix G′, as shown in FIG. 2a. In this case, r* is adjusted in accordance with the same sequence to obtain r′=(1.8, 1.6, −1.3, −1.0, −1.1, 0.9, 0.6, −0.5). Next, the newly generated generator matrix G′, and r′ are employed to obtain a tree for decoding. After completing the decoding process, the sequence of the corresponding adjusted bits is recovered back to the original.
A part of the decoding tree for decoding the linear block code is shown in FIG. 2b. As shown in the upper side of FIG. 2b, a table proposed by Larura Ekroot for calculating bit metrics is provided in addition. When both of (−1)c1 and ri are positive or negative, a bit metric Mb(ci, ri) corresponding to ci and ri is 0; or otherwise, the bit metric Mb(ci, ri) corresponding to ci and ri is the absolute value of ri. As shown in the lower side of FIG. 2b, contents of a stack required for A* decoding are provided.
At first, a path metric g(node 0) of the root node (node 0) of level 0 is assigned with 0. Emanating from node 0, there are two edges. One edge connects node 0 of level 0 and node 1 (representing c0=0) of level 1; and the other edge connects node 0 of level 0 and node 2 (representing c0=1) of level 1 respectively. It can be learnt from the table that the bit metric of c0=0 is Mb(c0=0, r0)=0, and the bit metric of c0=1 is Mb(c0=1, r0)=1.8. The path metrics of node 1 and node 2 are g(node 1)=g(node 0)+Mb(c0=0, r0)=0, and g(node 2)=g(node 0)+Mb(c0=1, r0)=1.8, respectively. Node 1 and node 2 are put in the stack. And then, one node, i.e., node 1 hereby, having the minimum path metric (the better path metric) is selected from node 1 and node 2 in the stack to be a pointer node. Hence, subsequent process starts from the pointer node, i.e., node 1.
Emanating from the pointer node (i.e., node 1 hereby), there are two edges which are connected to node 3 and node 4 of level 2 respectively. The path metric of node 3, g(node 3)=g(node 1)+Mb(c1=0, r1)=0, and the path metric of node 4, g(node 4)=g(node 1)+Mb(c1=1, ri)=1.6. The node 3 and node 4 are put in the stack and remain standby therein. The stack is arranged as the set of searched nodes according to partial path metrics of the nodes. A better path metric (i.e., smaller path metric in the current example) indicates a higher priority in the sequence. Therefore, node 4 is set beyond node 2. In the current stack, the nodes are sequentially ordered as node 3, node 4, and node 2. In a similar manner, node 3 having the minimum path metric in the stack is selected to be the pointer node, and the subsequent process starts from the pointer node, node 3. 100121 Emanating from the pointer node (i.e., node 3 hereby), there are two edges which are connected to node 5 and node 6 of level 3 respectively. The path metric of node 5, g(node 5)=g(node 3)+Mb(c2=0, r2)=1.3, and the path metric of node 6, g(node 6)=g(node 3) ±Mb(c2=1, r2)=0. The node 5 and node 6 are put in the stack and remain standby therein, and currently there are four nodes (node 2, node 4, node 5, and node 6) in the stack. In a similar manner, node 6 having the minimum path metric in the stack is selected to be the pointer node, and the subsequent process starts from the pointer node, node 6.
Emanating from the pointer node (i.e., node 6 hereby), there are two edges which are connected to node 7 and node 8 of level 4 respectively. The path metric of node 7, g(node 7)=1.0, and the path metric of node 8, g(node 8)=0. At level k=4, all information bits u0, u1, u2, u3 are determined, so that p4, p5, p6, p7 can be determined by the generator matrix G′. As such, the codewords passing through node 7 and node 8 have been respectively determined. Therefore, the paths represented by node 9 and node 10 of level 8 are determined. The path metric of node 9 is g(node 9)=1.6, and the path metric of node 10 is g(node 10)=1.4. The node of level n=8 is the goal node. However, the inferior goal node must be discarded. As such, if a present goal node having a path metric greater than the minimum path metric of all of the found goal nodes, the present goal node must be discarded, and at the same time, the best goal node having the minimum path metric is recorded. In this example, the minimum path metric of all the goal nodes that have been found is g(node 10)=1.4, and therefore currently there are two nodes, node 5 and node 10, in the stack.
Now, node 5 having the minimum path metric in the stack is selected to be the pointer node, and the subsequent process starts from the pointer node, node 5. It can be obtained that the path metric of node 11 is g(node 11)=2.3, and the path metric of node 12 is g(node 12)=1.3. Apparently, g(node 11)=2.3, is greater than the minimum path metric of the current goal nodes, g(node 10)=1.4, and therefore the path metric of node 11 should be discarded. Accordingly, currently there are two nodes, node 12 and node 10, in the stack.
In this case, node 12 now having the minimum path metric in the stack is selected to be the pointer node, and the subsequent process starts from the pointer node, node 12. It can be obtained that the path metric of node 13 is g(node 13)=3.9 which is greater than the minimum path metric of the current goal nodes, g(node 10)=1.4. Therefore the path metric of node 13 should be discarded. Accordingly. currently there is one node, i.e., node 10, in the stack.
In this case, the current stack has only one goal node, i.e., node 10, left. As such, the node 10 can be determined as the best one. Accordingly, the path c*=(u0, u1, . . . , uk−1, p0, p1, . . . , pn-k−1)=(00111100) of the node 10 is the maximum likelihood codeword. Finally, the sequence of r′ is recovered back to that of r, thus obtaining (00111010) and accordingly obtaining the information bits (0011).
Further, Yunghsiang S. Han has published a thesis titled “Efficient Priority-First Search Maximum-Likelihood Soft-Decision Decoding of Linear Block Codes” in volume 39 of IEEE Transactions on Information Theory (pages 1514 to 1523). Similar to the A* decoding procedure as disclosed by Laura Ekroot above, the starting steps of Yunghsiang S. Han can be learnt by referring to FIG. 2b. Further, in the method of Yunghsiang S. Han, the minimum Hamming distance between the codewords is employed.
As disclosed by Yungshiang S. Han, a decoded codeword is selected as a reference seed. Then, according to the order of sequences in the stack, and the minimum Hamming distance d, the nodes in the stack are sequentially calculated for obtaining corresponding bounds of estimated path metrics thereof. When a lower metric is desired, the bound is a lower bound. When the lower bound of the estimated path metric of the node is greater than the path metric of the reference seed, it can be determined that the best path does not pass through the instant node, and therefore the instant node can be eliminated from the current stack. The decoding method is executed until the maximum likelihood codeword having the minimum path metric is found.
With respect to the example of FIG. 2b, the reference seed is a path c* represented by node 10. The reference seed is selected during the decoding process, and in this case the node at the top of the stack is node 5. The distance between the partial path represented by node 5 and the corresponding part of c* is 1. Since the minimum Hamming distance of this (8, 4) extended Hamming code is d=4, the remaining part of each path passing through node 5 must include at least 3 additional bits different from the corresponding part in c*. Consider the best case, there are only three bits different from c* that may result in the minimum possible path metric. Specifically, three bits which are different from c* are selected from the non-decoded part subsequent to node 5, and the minimum possible accumulated edge metric thereof is calculated. In the current example, the last three bits (i.e., c5, c6, and c7) are different from c* for which the associated edge metrics are 0, 0.6, and 0, respectively. As such, the minimum possible accumulated edge metric (lower bound) is 0+0.6+0 =0.6. Adding the minimum possible accumulated edge metric 0.6 to the path metric 1.3 of node 5, the minimum possible path metric of the path passing through node 5 is obtained as 1.3+0.6=1.9, which is greater than the path metric 1.4 of c*. Therefore, it can be concluded that the best path won't pass through node 5. As such, node 5 should be eliminated from the stack.
Subsequently, the foregoing calculation is repeated for any node that is not a goal node in the stack.
Briefly, the method of Yunghsiang S. Han selects a decoded codeword serving as a reference seed, and utilizes the minimum Hamming distance between codewords to pre-estimate the minimum possible path metric of the possible codeword. In such a way, it can be previously learnt that which node should be discarded.
However, when utilizing the foregoing decoding method for decoding longer linear block codes, the decoding complexity thereof is still too high. As such, an improved decoding method for further reducing the decoding complexity is highly desired.